<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
// 快速排序的逻辑是，若要对 nums[lo..hi] 进行排序，
// 我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，
// 然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

/*
    function quick(arr,lo,hi){
      // 交换元素构建元素分界点 p 
      let p = partition(arr,lo,hi);
      quick(arr,lo,p-1);
      quick(arr,p+1,hi);
    }
*/
    
   

    // 再说说归并排序的逻辑，若要对 nums[lo..hi] 进行排序，
    // 我们先对 nums[lo..mid] 排序，
    // 再对 nums[mid+1..hi] 排序，
    // 最后把这两个有序的子数组合并，整个数组就排好序了。

    // 后序遍历?
    /*
    function mergeSort(arr,lo,hi){
      var mid = (lo+hi)/2;
      mergeSort(arr,lo,mid)
      mergeSort(arr,mid+1,hi)

      // 合并两个排好序的子数组
      merge(arr,lo,mid,hi)
    }
    */


    // 快速排序
    // 递归 构建 元素分界点,左边小,右边大
    function quickSort(arr){
      var len = arr.length;
      if(len<2){
        return arr
      }
      var mid = arr[0];
      var left = [];
      var right = [];
      for(var i = 0;i<len;i++) {
        if(arr[i]<mid){
          left.push(arr[i])
        }else{
          right.push(arr[i])
        }
      }
      return [...quickSort(left),mid,...quickSort(right)]
    }

    // 三路快排? 当面对一个有大量重复的数据的序列时，选取 mid 的快速排序有可能会退化成一个 O(n²) 的算法
    // left[]  mid[]  right[]  递归 left 与right 构建元素分界点

    // 递归为了两两比较,合并==> 左边与右边的比较合并
    function mergeSort(nums){
      
      var len = nums.length;
      if(len<2){
        return nums
      }
      var mid = Math.floor(len/2);
      var left = nums.slice(0,mid);
      var right = nums.slice(mid+1)
      return merge(mergeSort(left),mergeSort(right))
    }
    function merge(left,right){
      var res = [];
      while(left.length&&right.length){
        if(left[0]<right[0]){
          res.push(left.shift())
        }else{
          res.push(right.shift())
        }
      }
      // 合并 剩余 数组元素
      return res.concat(left,right)
    }
    
  </script>
</body>
</html>